#include <iostream>
#include <string>
#include <stdio.h>
using namespace std;

/* partial match table */
void init_table(const string &pattern, int *table)
{
    int len = pattern.length();
    table[0] = -1; /* -1 for easier calculation */
    for (int i = 1; i < len; i++) {
        /* get previous */
        int pos = table[i-1];
/*
 a b a c x x x a b a d a b a e
-1 0 0 1 0 0 0 0 1 2 3 0 1 2 3
                       * <== pos=3 -> pos=1 -> pos=0
*/
        while (pos >= 0) {
            /* compare with prefix */
            if (pattern[pos] == pattern[i-1]) {
                break;
            } else {
                /* find submatch */
#if 0
                if (table[pos] > 0) {
                    cout << "Find submatch with pos=" << pos << " & table[pos]=" << table[pos] << endl;
                }
#endif
                pos = table[pos];
            }
        }
        table[i] = pos + 1;
    }
}

/* O(n+m) */
int kmp_search(const string &target, const string &pattern)
{
    if (target.empty() || pattern.empty()) {
        return -1;
    }
    int tlen = target.length();
    int plen = pattern.length();
    if (tlen < plen) {
        return -1;
    }
    int *table = new int[plen];
    init_table(pattern, table);
#if 0
    for (int i = 0; i < plen; i++) {
        cout << " " << pattern[i];
    }
    cout << endl;
    for (int i = 0; i < plen; i++) {
        cout << table[i] << " ";
    }
    cout << endl;
#endif
    int i = 0, j = 0;
    while (i < tlen) {
        if (target[i] == pattern[j]) {
            i++;
            j++;
            if (j == plen) {
                delete[] table;
                return (i-plen); /* return index */
            }
        } else {
            if (table[j] >= 0) {
                j = table[j];
            } else {
                i++;
                j = 0;
            }
        }
    }
    delete[] table;
    return -1;
}

int main()
{
   string t = "abcabcabdabba";
   string p = "abcabd";
/*
 a b c a b d
-1 0 0 0 1 2
*/
   cout << "Find " << p << " in " << t << ": " << kmp_search(t, p) << endl;
   t = "cccabacxxxabadabae";
   p = "abacxxxabadabae";
/*
 a b a c x x x a b a d a b a e
-1 0 0 1 0 0 0 0 1 2 3 0 1 2 3
*/
   cout << "Find " << p << " in " << t << ": " << kmp_search(t, p) << endl;
   t = "aaaaaaaaaaaab";
   p = "ba";
/*
 b a
-1 0
*/
   cout << "Find " << p << " in " << t << ": " << kmp_search(t, p) << endl;
   return 0;
}
